package org.aplombh.java.leetcode.all;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

public class _37解数独 {
    public static void main(String[] args) {

//        System.out.println("1&2 "+ (1&2));
//        System.out.println("1|2 "+ (1|2));
//        System.out.println("1^2 "+ (1^2));
//        System.out.println("1^1 "+ (1^1));

        char[][] chars = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        new Solution37_2().solveSudoku(chars);
        for (char[] aChar : chars) {
            for (char c : aChar) {
                System.out.print(c+" ");
            }
            System.out.println();
        }
    }
}

class Solution37_1 {
    private final boolean[][] line = new boolean[9][9];
    private final boolean[][] column = new boolean[9][9];
    private final boolean[][] block = new boolean[9][9];

    private boolean valid = false;
    private final List<Pair<Integer, Integer>> spaces = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    // 将所有空位置添加进spaces
                    spaces.add(new Pair<>(i, j));
                } else {
                    // 将所有已知位置
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3 + j % 3][digit] = true;
                }
            }
        }
        dfs(board, 0);
    }

    public void dfs(char[][] board, int idx) {
        if (idx == spaces.size()) {
            valid = true;
            return;
        }

        Pair<Integer, Integer> space = spaces.get(idx);

        int i = space.getKey(), j = space.getValue();

        // 从0开始依次尝试赋值
        for (int digit = 0; digit < 9 && !valid; ++digit) {
            // 判断当前位置是否合法
            if (!line[i][digit] && !column[j][digit] && !block[i / 3 * 3 + j / 3][digit]) {
                // 赋值
                line[i][digit] = column[j][digit] = block[i / 3 * 3 + j / 3][digit] = true;
                board[i][j] = (char) (digit + '0' + 1);
                // 递归
                dfs(board, idx + 1);
                // 回溯
                line[i][digit] = column[j][digit] = block[i / 3 * 3 + j / 3][digit] = false;
            }
        }
    }
}

//
class Solution37_2 {
    private final int[] line = new int[9];
    private final int[] column = new int[9];
    private final int[] block = new int[9];
    private boolean valid = false;
    private final List<Pair<Integer, Integer>> spaces = new ArrayList<>();

    public void flip(int i, int j, int digit) {
        // ^ 异或 不同为1,方便回溯
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i / 3 * 3 + j / 3] ^= (1 << digit);
    }

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.add(new Pair<>(i, j));
                } else {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }
        dfs(board, 0);
    }

    public void dfs(char[][] board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }

        Pair<Integer, Integer> space = spaces.get(pos);
        int i = space.getKey(), j = space.getValue();

        // 找到所有满足情况情况
        int mask = ~(line[i] | column[j] | block[i / 3 * 3 + j / 3]) & 0x1ff;
        // 循环遍历每种情况  -(b&-b)-> 0101 & 1011 = 0001  -(b&(b-1))-> 0101 & 0100 = 0100
        for (; mask != 0 && !valid; mask &= (mask - 1)) {

            // 找到末尾符合条件的位置,然后插入数
            int digitMask = mask & (-mask);
            // 二进制数转换为十进制
            int digit = Integer.bitCount(digitMask - 1);
            // 将二进制更新
            flip(i, j, digit);
            // 将该位置放入数
            board[i][j] = (char) (digit + '0' + 1);
            // dfs
            dfs(board, pos + 1);
            // 回溯
            flip(i, j, digit);
        }
    }
}